package com.example.leetcode.dp;

public class Test416 {


    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i :nums) {
            sum += i;
        }
        if (sum % 2 ==1 ){
            return false;
        }
        if (nums[0] == sum /2){
            return true;
        }
        boolean[][] dp = new boolean[nums.length][sum /2 + 1];
        dp[0][0] = true;
        if (nums[0] < sum/2){
            dp[0][nums[0]] = true;
        }
        for (int i =1;i<nums.length;i++){
            for (int j = 0;j<=sum/2;j++){
                if (dp[i-1][j] ||( j -nums[i] >=0 && dp[i-1][j -nums[i]])){
                    dp[i][j] = true;
                }
                if (j == sum /2){
                    return true;
                }
            }
        }
        return false;
    }
}
